/**
 * 选择排序（Selection sort）
 *
 * ---------------------------------
 * 文档查看: /document/algo/sort_selection.md
 * 2021-01-22
 */
#include <stdio.h>
// 这里应该使用 .h 的文件的，但是因为 `Code runner`会编译不过去，就用 .c 。
// 因为我们仅有一个入口文件调用，可用使用 .c ，知道就可以了，我是为了学习思路的。
#include "../utils/c_tool.c"
// #include "../utils/c_tool.h"

int * SelectionSort(int array[], int length) {
  clock_t start, end;
  /*记录循环开始的时间*/
  start = clock();
  
  for (int i = 0; i < length - 1; i++) {
    int maxLength = length - i - 1;
    int max = maxLength;
    int min = i;

    for (int j = i + 1; j < length - i; j++) {
      min = array[min] > array[j] ? j : min;
      max = array[max] < array[j] ? j : max;
    }

    if (min != i) {
      ToolSwap(array, min, i);
    }

    if (max != maxLength) {
      ToolSwap(array, max, maxLength);
    }
  }
  /*记录循环结束的时间*/
  end = clock();
  ToolPrintRunTime(start, end);
  return array;
}


int main() {
  int nums[] = {1, 4, 7, 5, 3, 2, 9};
  int length = sizeof(nums)/sizeof(nums[0]);
  printf("选择排序: \n");
  printf("初始化数据为");
  ToolPrintArray(nums, length);

  int * result = SelectionSort(nums, length);

  printf("\n 结果为");
  ToolPrintArray(result, length);
}